package MonotoneStack;
/*
 * 下一个更大元素 II
 */
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class lc503 {

    public int[] nextGreaterElements(int[] nums) {
        if(nums == null || nums.length <= 1) {
            return new int[]{-1};
        }
        int len = nums.length;
        int[] res = new int[len];
        Arrays.fill(res, -1);
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < len * 2; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i % len]) {
                res[stack.peek()] = nums[i%len];
                stack.pop();
            }
            stack.push(i % len);
        }
        return res;

    }

}
